#include "Lse.h"
#include "Rse.h"


Lse::Lse(Tree* G, Distance* distance1)
{
	distance = distance1;
	Table= new vector<Tree*>[G->getSize()+1];
	ForestSize = new vector<int>[G->getSize()+1];
	inTree=G;
	Right_To_Left_Preorder_Traversal(G,true);
	find_Lse(G);
}

Lse::~Lse()
{
	delete []Table;
}

void Lse::Right_To_Left_Preorder_Traversal(Tree* G, bool restart)
{
	static int counter;
	int i;
	if(restart)
		counter=0;
	if(G==NULL)
		return;
	G->getData()->setRTLP(counter++);
	for(i=G->getChildrenCount()-1; i>=0 ; i--)
	{
		Right_To_Left_Preorder_Traversal(G->getChild(i) , false);
	}
}


void Lse::Convert(vector<int>* T, Rse& rse)
{
	int** temp;//temporery place to hold the values of T
	temp = new int*[rse.GetT()->getSize()+1];
	for(int i=0; i<rse.GetT()->getSize()+1 ; i++)
	{
		temp[i] = new int[T[i].size()];
		for(int j=0; j < T[i].size() ; j++)
		{
			temp[i][j]=T[i][j];
		}
		//clear all values of T and put zeros instead
		T[i].clear();
		for(int j=0; j<=get_JofI(i); j++)
		{
			T[i].push_back(0);
		}
	}
	//transform T to RSE from LSE
	for(int i=0; i<GetT()->getSize()+1 ; i++)
	{
		for(int j=0; j<=rse.get_JofI(i) ; j++)
		{
			int i1,j1;
			i1 = rse.GetForest(i,j)->getData()->getRTLP();
			j1 = i+j-i1;
			T[i1][j1] = temp[i][j];
		}
	}

	for(int i=0; i<rse.GetT()->getSize()+1 ; i++)
		delete[] temp[i];
	delete[] temp;
}

void Lse::find_Lse(Tree* G)
{
	for (int i=G->getSize(); i>=0; i--)
	{
		currSize = G->getData()->getDT();
		DeleteRightVertex(i,G);
		DeleteLeftVertex(i,(G->getSize()+1)-i-(W.GetRightTree()->getSize()+1));
	}
}

void Lse::DeleteRightVertex(int i,Tree* G)//delete i Rightmost Vertexes
{
	if(i==0)
	{
		W.AddRightTree(G);
		return;
	}
	currSize -= distance->DeleteNode(G);
	if(G->getRight()==NULL)
	{
		Tree* temp;
		temp=W.GetRightTree();
		W.RemoveRightTree();
		DeleteRightVertex(i-1,temp);
	}
	else
	{
		for(int k=0; k < G->getChildrenCount()-1 ; k++)
			W.AddRightTree(G->getChild(k));
		DeleteRightVertex(i-1,G->getRight());
	}
}


void Lse::DeleteLeftVertex(int i,int j)
{
	ForestSize[i].push_back(currSize);
	if(j==0)
	{
		Table[i].push_back(W.GetLeftTree());
		W.RemoveRightTree();  //remove the last tree in the forest W
	}
	else
	{
		currSize -= distance->DeleteNode(W.GetLeftTree());
		Table[i].push_back(W.GetLeftTree());
		if(W.GetLeftTree()->getLeft()==NULL)
		{
			W.RemoveLeftTree();
			DeleteLeftVertex(i,j-1);
		}
		else
		{
			Tree* temp=W.GetLeftTree();
			W.RemoveLeftTree();
			for(int k=temp->getChildrenCount()-1 ; k>=0 ; k--)
				W.AddLeftTree(temp->getChild(k));
			DeleteLeftVertex(i,j-1);
		}
	}
}

Tree* Lse::GetForest(int i,int j)
{
	return Table[i][j];
}

int Lse::get_JofI(int i)
{
	return inTree->getSize()-i-Table[i].back()->getSize();
}

int Lse::getForestSize(int i, int j)
{
	return ForestSize[i][j];
}